package class02;

import java.util.ArrayList;

/**
 * 1 输入链表的头节点，奇数个找中点，偶数个找上一个中点 eg abcd 返回b；
 * 2 输入链表的头节点，奇数个找中点，偶数个找下一个中点 eg abcd 返回c
 * 3  输入链表的头节点 奇数个返回中点的前一个节点，偶数个返回上中点的前一个节点
 * 4  输入链表的头节点 奇数个返回中点的前一个节点，偶数个返回下中点的前一个节点
 */
public class Code01_FindMid {
    // 构造节点
    static class Node {
        int value;
        Node next;

        Node(int value) {
            this.value = value;
        }


        //1
        Node midOrUpMidNode(Node head) {
            if (null == head || null == head.next || null == head.next.next) {
                return null;
            }
            Node slow = head.next;
            Node fast = head.next.next;

            while (null != fast.next && null != fast.next.next) {
                slow = slow.next;
                fast = fast.next.next;
            }
            return slow;
        }
        // 容器实现
        Node right1(Node head) {
            if (head == null) {
                return null;
            }
            Node cur = head;
            ArrayList<Node> arr = new ArrayList<>();
            while (cur != null) {
                arr.add(cur);
                cur = cur.next;
            }
            return arr.get((arr.size() - 1) / 2);
        }

        Node midOrDownMidNode(Node head) {
            if (head == null || head.next == null) {
                return head;
            }
            Node slow = head.next;
            Node fast = head.next;
            while (fast.next != null && fast.next.next != null) {
                slow = slow.next;
                fast = fast.next.next;
            }
            return slow;
        }

        Node midOrUpMidPreNode(Node head) {
            if (head == null || head.next == null || head.next.next == null) {
                return null;
            }
            Node slow = head;
            Node fast = head.next.next;
            while (fast.next != null && fast.next.next != null) {
                slow = slow.next;
                fast = fast.next.next;
            }
            return slow;
        }

        Node midOrDownMidPreNode(Node head) {
            if (head == null || head.next == null) {
                return null;
            }
            if (head.next.next == null) {
                return head;
            }
            Node slow = head;
            Node fast = head.next;
            while (fast.next != null && fast.next.next != null) {
                slow = slow.next;
                fast = fast.next.next;
            }
            return slow;
        }
    }

    public static void main(String[] args) {
        Node test = null;
        test = new Node(0);
        test.next = new Node(1);
        test.next.next = new Node(2);
        test.next.next.next = new Node(3);
        test.next.next.next.next = new Node(4);
        test.next.next.next.next.next = new Node(5);
        test.next.next.next.next.next.next = new Node(6);
        test.next.next.next.next.next.next.next = new Node(7);
        test.next.next.next.next.next.next.next.next = new Node(8);

        Node ans1 = null;
        Node ans2 = null;
        ans1 = test.midOrUpMidNode(test);
        ans2 = test.right1(test);
        System.out.println(ans1 != null ? ans1.value : "无");
        System.out.println(ans2 != null ? ans2.value : "无");

        ans1 = test.midOrDownMidNode(test);
        System.out.println(ans1 != null ? ans1.value : "无");


        ans1 = test.midOrUpMidPreNode(test);
        System.out.println(ans1 != null ? ans1.value : "无");

        ans1 = test.midOrDownMidPreNode(test);
        System.out.println(ans1 != null ? ans1.value : "无");
    }
}